public class LongestPalindrome {
    public static void main(String[] args) {
        String s = "aaaaa";

        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int begin = 0, max = 1;
        for (int i = 0; i < n; ++i) {
            dp[i][i] = true;
            if (i < n - 1 && s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                max = 2;
                begin = i;
            }
        }

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 2; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                }

                int len = j - i + 1;

                if (dp[i][j] && len > max) {
                    max = len;
                    begin = i;
                }

                System.out.println("begin: " + begin + ", max: " + max);
            }
        }
        System.out.println(s.substring(begin, begin + max));
    }

}
